Finite Automata

History of Finite Automata:

The fact that finite automata has become a discipline of computer science demonstrates the breadth of its applications. A group of biologists, psychologists, mathematicians, engineers, and some of the first computer scientists were among the first to examine the concept of a finite state machine. The members of this group had a common interest in modelling human mental processes, whether in the brain or on a computer. Warren McCulloch and Walter Pitts, two neurophysiologists, were the first to describe finite automata in 1943. Their research paper, "A Logical Calculus Immanent in Nervous Activity," contributed significantly to the fields of neural network theory, automata theory, computation theory, and cybernetics. Later on in this study, G.H. Mealy and E.F.

Theory of Automata

Theoretical computer science and mathematics combine to form the theory of automata. It is the study of abstract machines and the issues that these machines can answer in terms of computing. The automaton is a type of abstract machine. The primary motivation for automata theory development was to create tools for describing and analysing the dynamic behaviour of discrete systems.

States and transitions make up this automaton. The Transitions are depicted by arrows, while the State is represented by circles.

Automata is a type of machine that accepts a string as input and passes it through a finite number of states before arriving at the end state.

Symbols:

Symbols are an entity which can be any letter, picture or alphabet. 

e.g     x, y, #,1, etc..

Alphabets:

Alphabets are a finite set of symbols. and It is denoted by ∑

e.g. ∑ =  {x, y, z}    , ∑ = {1,5,4,9,7}

String:

It is a finite collection of symbols from the alphabet. The string is denoted by w.

If ∑ = {a, b}, various string that can be generated from ∑ are {ab, aa, aaa, bb, bbb, ba, aba.....}.

• A string with zero occurrences of symbols is known as an empty string. It is represented by ε.
• The number of symbols in a string w is called the length of a string. It is denoted by |w|.

Finite Automata : 

Finite Automata is the most basic machine for pattern recognition. A finite automaton, often known as a finite machine, is a five-tuple abstract machine. it has a set of states and rules for moving from one particular state to another but it depends upon the applied input symbol. Basically, it is an abstract model of a digital computer.

A finite automaton is a collection of 5-tuple (Q, ∑, δ, q0, F), where:

Q : Finite set of states

∑ : Finite set of the input symbol

q0 : initial state

F : Final state

δ : Transition Function

Finite automata can be represented by input tape and finite control.

Input tape: It is a linear tape having some number of cells and Each input symbol is placed in each cell.

Finite control: The finite control determine the next state on receiving particular input from input tape. The tape reader reads the cells one by one from left direction to right, and at a time only one input symbol is read. 

Finite Automata Representation : 

The finite automata can be represented in three ways, as given below −

• Graphical (Transition diagram)
• Tabular (Transition table)
• Mathematical (Transition function)

Transition Diagram

A transition diagram is a directed graph which can be constructed as follows:

• There is a node for each state in Q, which is represented by the circle.
• There is a directed edge from node q to node p labeled a if δ(q, a) = p.
• In the start state, there should be an arrow with no source.
• Final states or Accepting states are indicating by a double circle.

Transition Table

The transition table is a table that shows how the transition function works.

and it returns a state after taking two parameters, such as a state and a symbol (the "next state").

A transition table is represented by the following things:

• The start state is denoted by an pointing arrow with no source.
• The accept state is denoted by a star.

example...

Transiton Table for above digram will be....

 

Present State	Next state for Input 0	Next State of Input
→q0	q1	q2
q1	q0	q2
*q2	q2	q2

   

Transition function

The transition function is denoted by δ. The two parameters mentioned below are the passes to this transition function.

1. Current state
2. Input symbol

The transition function returns a state which can be called as the next state.

δ (current state, current input symbol) = next state

            For example, δ(q0,a) = q1 

Types of Finite Automata:

1. deterministic finite automata  (DFA)
2. non-deterministic finite automata  (NFA)

1. Deterministic finite automata (DFA)

Deterministic finite automata (DFA) is an acronym for deterministic finite automata. The machine in the DFA only moves to one state for a single input character. 

The Null move is not accepted by DFA.

DFA consists of 5 tuples (Q, ∑, δ, q0, F)

Q : Finite set of states

∑ : Finite set of the input symbol

q0 : initial state

F : Final state

δ : Transition Function, defined as δ X ∑  -> Q

Example..

    below is example of DFA with ∑ = {0, 1} accepts all strings starting with 1.

there can be many possible DFA's for a pattern but a DFA with a minimum number of states is generally preferred.

2. Non-deterministic finite automata (NFA) 

Non-deterministic finite automata (NFA) is an acronym for non-deterministic finite automata. It can be used to send any number of states for a single input. It is capable of accepting the Null move.

It is capable of progressing without the use of symbols. NFA has a distinct transition function due to these extra features, but the rest is the same as DFA.

DFA consists of 5 tuples (Q, ∑, δ, q0, F)

Q : Finite set of states

∑ : Finite set of the input symbol

q0 : initial state

F : Final state

δ : Transition Function, defined as δ X ∑  -> 2^Q

Example..

    below is the example of NFA with ∑ = {0, 1} accepts all strings starting with 1.

Difference Between DFA and NFA

SR. No.	DFA	NFA
1	It is not competent in handling an Empty String transition	It is competent to handle an empty string transition.
2	It can be defined as one machine.	Multiple machines execute computational tasks at the same time.
3	In DFA, backtracking is allowed.	In NFA, backtracking is not allowed.
4	In DFA, empty string transitions are not noticed.	It allows empty string transition.
5	It is tough to construct a DFA.	It is easy to construct a NFA.
6	It needs more space.	It needs less space.
7	The complete time needed for managing any input string in DFA is shorter than NFA.	The complete time needed for managing any input string in NFA is larger than DFA.
8	All DFA are considered as NFA.	All NFA are not considered as DFA.

Applications of Finite Automata :

• For the designing of lexical analysis of a compiler.
• For recognizing the pattern using regular expressions.
• For the designing of the combination and sequential circuits using Mealy and Moore Machines.
• Used in text editors.
• For the implementation of spell checkers.
• For design a text editors.
• For design Lexical Analyzers.

Thank you ! 😃

Blog BY:

1) Aditya Sabde
2) Rutuja Shinde
3) Tanmay Sharma
4) Abhishek Tayde